package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * 复原 IP 地址
 * @author qulq
 * @date 2024-07-07 17:06:23
 */
public class T93_RestoreIpAddresses{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new T93_RestoreIpAddresses().new Solution();
		 System.out.println(solution.restoreIpAddresses("25525511135"));
		 System.out.println(solution.restoreIpAddresses("0000"));
		 System.out.println(solution.restoreIpAddresses("101023"));
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	List<String> ans = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
		if (s.length() < 4 || s.length() > 12) {
			return ans;
		}
		backtracking(s, 0, 0, "");
		return ans;
    }

	private void backtracking(String s, int start, int pointNum, String path) {
		if (pointNum == 3) {
			// start < s.length()；最后一个点必须在最后一个数字之前，防止101023前3下切成10.10.23，最后一位是空的情况。
			if (start < s.length() && isValid(s.substring(start))) {
				ans.add(path + s.substring(start));
			}
			return;
		}
		for (int i = start; i < s.length(); i++) {
			// 剪枝：长度大于3时，该层的所有其他组合肯定不满足
			if (i - start + 1 > 3) {
				break;
			}
			if (isValid(s.substring(start, i + 1))) {
				backtracking(s, i + 1, pointNum + 1, path + s.substring(start, i + 1)+ ".");
			}
		}
	}

	private boolean isValid(String s) {
		if (s.length() > 1 && s.charAt(0) == '0') {
			return false;
		}
		int num = Integer.parseInt(s);
		if (num > 255) {
			return false;
		}
		return true;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}